﻿using System;
using System.Collections.Generic;
using System.Runtime.CompilerServices;
using System.Text;

namespace LinkedDemo
{
    public class Linked<T>
    {
        Node header = null;
        public bool Add(T t)
        {
            Node node = new Node(t);
            if (header == null)
            {
                header = node;
                return true;
            }
            Node temp = header;
            while (temp.Next != null)
            {
                temp = temp.Next;
            }
            temp.Next = node;
            return true;
        }

        public bool Remove(T t)
        {
            if (header == null)
            {
                return false;
            }
            Node delNode = new Node(t);
            if (header.getValue().Equals(delNode.getValue()))
            {
                header = header.Next;
            }
            Node tempNode = header;
            while (tempNode.Next != null)
            {
                if (tempNode.Next.getValue().Equals(delNode.getValue()))
                {
                    tempNode.Next = tempNode.Next.Next;
                }
                else
                {
                    tempNode = tempNode.Next;
                }
            }
            return true;
        }

        public String Reverse()
        {
            Node pre = null;
            Node next = null;
            while (header != null)
            {
                next = header.Next;
                header.Next = pre;
                pre = header;
                header = next;
            }

            StringBuilder sb = new StringBuilder();
            sb.Append("[");
            sb.Append(pre.getValue());
            Node temp = pre.Next;
            while (temp != null)
            {
                sb.Append(" ," + temp.getValue());
                temp = temp.Next;
            }
            sb.Append("]");
            return sb.ToString();
        }

        public int Count()
        {
            int index = 0;
            if (header == null)
            {
                return index;
            }
            index++;
            Node temp = header.Next;
            while (temp != null)
            {
                index++;
                temp = temp.Next;
            }
            return index;
        }

        public override String ToString()
        {
            if (header == null)
            {
                return "[]";
            }
            int index = 0;
            StringBuilder sb = new StringBuilder();
            sb.Append("[");
            sb.Append(header.getValue());
            Node temp = header.Next;
            while (temp != null)
            {
                sb.Append(" ," + temp.getValue());
                temp = temp.Next;
                index++;
                if (index > 20)
                {
                    break;
                }
            }
            sb.Append("]");
            return sb.ToString();
        }

        public void CreateRing()
        {
            int count = Count();
            if (count > 0)
            {
                decimal halfPoint = Math.Ceiling(Convert.ToDecimal(count / 2));
                Node temp = header;
                Node halfNode = null;

                int i = 0;
                while (temp.Next != null)
                {
                    if (i == Convert.ToInt32(halfPoint))
                    {
                        halfNode = temp;
                    }
                    temp = temp.Next;
                    i++;
                }
                temp.Next = halfNode;
            }
        }

        public bool ExistsRing()
        {
            if (header == null)
            {
                return false;
            }
            Node slow = header;
            Node fast = header.Next;
            while (slow != null && fast != null)
            {
                if (slow.getValue().Equals(fast.getValue()))
                {
                    return true;
                }
                slow = slow.Next;
                fast = fast.Next.Next;
            }
            return false;
        }

        public Linked<int> Union(Linked<int> l1, Linked<int> l2)
        {
            if (l1.header == null) return l2;
            if (l2.header == null) return l1;
            Linked<int> head = null;
            if (l1.header.getValue() <= l2.header.getValue())
            {
                head = l1;
                Linked<int> temp = new Linked<int>();
                temp.header = l1.header.Next;
                head.header.Next = Union(temp, l2).header;
            }
            else
            {
                head = l2;
                Linked<int> temp = new Linked<int>();
                temp.header = l2.header.Next;
                head.header.Next = Union(l1, temp).header;
            }
            return head;
        }

        public bool RemoveLastAt(int index)
        {
            if (header == null) return true;
            if (index < 0 || index > Count() - 1) return true;
            Node fast = header;
            for (int i = 0; i < index; i++)
            {
                fast = fast.Next;
            }
            Node slow = header;
            while (fast.Next != null)
            {
                fast = fast.Next;
                slow = slow.Next;
            }
            slow.Next = slow.Next.Next;
            return true;
        }

        public bool IsPalindrome()
        {
            if (header == null) return true;
            Node slow = header;
            Node fast = header;
            while (fast.Next != null)
            {
                fast = fast.Next.Next;
                slow = slow.Next;
            }
            Node pre = null;
            Node next = null;
            while (slow != null)
            {
                next = slow.Next;
                slow.Next = pre;
                pre = slow;
                slow = next;
            }
            Node temp = header;
          
            while (temp != pre)
            {
                if (!temp.getValue().Equals(pre.getValue()))
                {
                    return false;
                }
                if (temp.Next == pre)
                {
                    return true;
                }
                temp = temp.Next;
                pre = pre.Next;
            }
            return true;
        }

        class Node
        {
            private T value;
            public Node(T _value)
            {
                this.value = _value;
            }
            public T getValue()
            {
                return this.value;
            }
            public Node Next { get; set; }
        }
    }
}
